package com.ls.que101_105;

import com.ls.utils.TreeNode;

/**
 * @author ：ls
 * @date ：2022/3/20 18:42
 * @description：...
 */
public class BuildTree {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return gen(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }

    public TreeNode gen(int[] preorder, int pl, int pr, int[] inorder, int il, int ir){
        if (pl > pr || il > ir)
            return null;

        // 找出当前节点
        TreeNode now = new TreeNode(preorder[pl]);

        // 在中序遍历中分割左右子树
        int k=0;
        for (int i=il; i<=ir;i++){
            if (inorder[i] == preorder[pl]){
                k = i;
                break;
            }
        }

        // 左子树的长度
        int len_l = k - il;
        int len_r = ir - k;

        // 进行下一次的循环
        // 左子树
        now.left = gen(preorder, pl+1, pl + len_l, inorder, il, k-1);
        // 右子树
        now.right = gen(preorder, pl+1+len_l, pl + len_l + len_r, inorder, k+1, ir);
        return now;
    }

//    public static void main(String[] args) {
//        TreeNode treeNode = null;
//        gen(treeNode);
//        System.out.println(treeNode.val);
//    }
//
//    public static void gen(TreeNode node){
//        node = new TreeNode(1);
//    }
}
